Problema de ajedrez de las ocho reinas.

    Recursividad.
            Función factorial.
            Función fibonacci.
            Función torres de hanoi.

    Algoritmo de backtracking.

    Búsqueda en profundidad.

# include <stdio.h>
long factorial(long);

main()
{
  int i;

 printf(“Digite un entero: “);
 scanf(“%ld”, &n);
 for(i = 1;i <= n; i ++)
 printf(“%2d! = %ld\n”,i ,factorial(i));
  return 0;
}
 

/* Definición recursiva de la función factorial*/

long factorial(long number)
{
  if (number <= 1)
       return 1;
   else
        return (number * factorial (number-1));
}

# include <stdio.h>
long fibonacci(long);

main()
{
   long result, number;

   printf(“Digite un entero: “);
  scanf(“%ld”, &number);
  result = fibonacci(number);
  printf(“Fibonacci(%ld) = %ld\n”, number, result);
  return 0;
}
 

/*Definiciòn de la función fibonacci*/

long fibonacci(long n)
{
   if (n==0 || n==1)
       return n;
   else
       return fibonacci(n-1) + fibonacci(n-2);
}

Hanoi(entero positivo n, poste i, poste j, poste k)

1 si n=1 entonces
2 mover disco superior del poste i al poste k
3 sino
4 hanoi (n-1,i,k,j)
5 mover el disco superior del poste i al poste k
6 hanoi (n-1,j,i,k)

Usando una pila para almacenar y luego recuperar los nodos marcados de un grafo, puede llevarse a cabo una búsqueda en profundidad del grafo. El algoritmo que se obtiene a continuación, en ves de emplear explícitamente una pila, se utiliza recursión para asegura que los nodos marcados son considerados en orden LIFO. Una vez, usamos un array d [1..|V|] para mantener los nodos marcados. Sin embargo, ahora consideraremos un nodo v como no marcado si d[v] = a 0 y marcados si su componente almacena cualquier otro valor. el valor real eventualmente almacenado en d[v] vendrá dado por el momento de tiempo en el cual el nodo v es descubierto durante la búsqueda. Así, debe utilizarse una variable global denominada tiempo para llevar cuenta del tiempo. Además de mantener los momentos de descubrimiento de los nodos usando el array d, también encontraremos tener útil mantener el momento en el que el tratamiento de un nodo es completado. El siguiente algoritmo usa un array  ¦ [1..|V|] para almacenar estos tiempo de terminación.

Debido a que esto es una búsqueda en profundidad, una vez que un nodo origen s es seleccionado, al algoritmo buscara en el grafo con mayor profundidad (desde s) hasta que ya no pueda encontrar un nodo no marcado. En este punto, si hay nodos restantes no marcados, se selecciona uno de ellos como el nuevo origen para seguir buscando. El algoritmo BEP () ofrecido a continuación es responsable inicialmente de hacer que todos los nodos estén no marcados y de escoger los nodos origen. En realidad invoca al algoritmo BEP Visita () para realizar la búsqueda en profundidad desde cada origen. La llamada recursiva se hacen desde BEP – Visita () en la línea cuatro, devolviendo el control a BEP () solo después de que todos los nodos no marcados accesibles desde un origen s hayan sido marcados.

BEP (Grafo G = (V,E))
1 para cada v Î V hacer
2      d[v]  0          todos los nodos están sin descubrir (i.e....,sin marcar)
3 tiempo   0          tiempo es una variable global
4 para cada s Î V hacer
5         si d[s] = 0 entonces       ¿esta marcado el nodo s?
6                  BEP – Visita (G,s)
 

BEP – Visita (Grafo G = (V,E), nodo s)          s es el origen
1. d[s]  tiempo  tiempo + 1        el nodo  s es descubierto y marcado
2. para cada m Î adyacente [s] hacer
3. si d[m] = 0 entonces      ¿esta marcado el nodo m?
4.           BEP-Visita (G, m)
5. ¦ [s]  tiempo  tiempo + 1     terminamos con el nodo s
 

Obsérvese como la variable tiempo se inicializa en la línea 3 de BEP () y que es primero incrementada antes de asignarla a d [s] o ¦ [s] en la línea 1 y 5 de BEP – Visita (). El lector debería también observar que el bucle de las líneas 4 – 6 de BEP () garantiza que todo nodo del grafo será eventualmente marcado e incluso si el grafo no es conexo. Este algoritmo también puede ser aplicado a grafos no dirigidos, así como valorados. Es fácil ver que el tiempo de ejecución de BEP () es  -  (V + E). Para cada nodo v Î V, BEP – Visita () es invocado exactamente una vez; y en cada una de estas llamadas el bucle de las líneas 2 – 4de BEP – Visita () considerada cada nodo adyacente a v. Como el tamaño de todas   -  (E), obtenemos el tiempo de ejecución lineal - (V + E).